package Leetcode;

public class problem5 {
    public static String longestPalindrome(String s) {
        if(s == null || s.length() <= 1){
            return s;
        }

        StringBuilder sb = new StringBuilder("$#");
        for(int i = 0;i < s.length();i++){
            sb.append(s.charAt(i));
            sb.append("#");
        }

        char[] str = sb.toString().toCharArray();

        //回文串中能达到最右的位置
        int mx = 0;
        //最长回文串的中心点
        int position = 0;
        int resLen = 0;
        int resCenter = 0;
        int[] p = new int[str.length];

        for(int i = 1;i < str.length;i++){
            p[i] = mx > i ? Math.min(p[2*position - i], mx - i) : 1;
            while(i+p[i] < str.length && i - p[i] >= 0 && str[i+p[i]] == str[i-p[i]]){
                p[i]++;
            }

            if(mx < i + p[i]){
                position = i;
                mx = i + p[i];
            }

            if(resLen < p[i]){
                resLen = p[i];
                resCenter = i;
            }
        }

        return s.substring((resCenter - resLen) / 2 , (resCenter - resLen) / 2+resLen - 1);

    }

    public static void main(String[] args) {
        String s = "aaabaaaa";
        System.out.println(s.substring(0,7));
        System.out.println(longestPalindrome(s));
    }
}
